package com.yangzhe.algorithm.c034;

// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
public class Code05_LinkedListCycleII_LeetCode {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    /**
     * 实现方法是使用快慢指针，流程如下。小学奥数追及问题，记住流程即可，证明一般不会考
     * 1. 快指针走两步，慢指针走一步
     * 2. 快慢指针第一次相遇后，快指针改到链表头部
     * 3. 快指针也走一步
     * 4. 快慢指针第二次相遇就是入环节点
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        ListNode ans = null;

        // 有空证明不成环
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        // 快慢指针，如果能相遇则证明成环了，并且此时slow在追逐路程的中间点
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (fast != slow) {
            slow = slow.next;
            // 有为空的节点证明不成环
            if (fast.next == null) {
                return null;
            }
            if (fast.next.next == null) {
                return null;
            }
            fast = fast.next.next;
        }

        // fast回到起点，和slow走同样的路程，就会到达入环点
        fast = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }

}
